package com.lbx.algo.sort;

/**
 * 二分查找
 */
public class BinarySearch {

    public static int binarySearch(int[] nums,int value){
        int low = 0;
        int high = nums.length-1;
        while(low <= high){
            int mid = low +((high-low)>>1);
            if(nums[mid] == value){
                return mid;
            }else if(nums[mid] < value){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }
        return -1;
    }

    // 二分查找的递归实现
    public static int bsearch(int[] a, int n, int val) {
        return bsearchInternally(a, 0, n - 1, val);
    }

    private static int bsearchInternally(int[] a, int low, int high, int value) {
        if (low > high) return -1;

        int mid =  low + ((high - low) >> 1);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            return bsearchInternally(a, mid+1, high, value);
        } else {
            return bsearchInternally(a, low, mid-1, value);
        }
    }

    //变体一：查找第一个值等于给定值的元素
    public static int bsearch1(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        if (low < n && a[low]==value) return low;
        else return -1;
    }
    public static int bsearch2(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if(a[mid] < value){
                low = mid + 1;
            }else{
                if(mid == 0 || a[mid-1] != value){
                    return mid;
                }else{
                    high = mid-1;
                }
            }
        }
        return -1;
    }

    //查找最后一个值等于给定值的元素
    public static int bsearch3(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if(a[mid] < value){
                low = mid + 1;
            }else{
                if(mid == n-1 || a[mid+1] != value){
                    return mid;
                }else{
                    low = mid+1;
                }
            }
        }
        return -1;
    }

    //查找第一个大于等于给定值的元素
    public static int bsearch4(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) {
                if ((mid == 0) || (a[mid - 1] < value)) return mid;
                else high = mid - 1;
            } else if(a[mid] < value){
                low = mid + 1;
            }
        }
        return -1;
    }

    //查找最后一个小于等于给定值的元素
    public static int bsearch5(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else {
                if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,6,6,7,8,8,9};
        System.out.println(bsearch2(nums,nums.length,8));
        System.out.println(bsearch3(nums,nums.length,9));
        System.out.println(bsearch4(nums,nums.length,5));
        System.out.println(bsearch5(nums,nums.length,5));
    }
}
